package orderedMap

import (
	"bytes"
	"fmt"
	"reflect"
	"myMap"
	"sort"
)


type Keys interface {
	sort.Interface
	Add(k interface{}) bool
	Remove(k interface{}) bool
	Clear()
	Get(index int) interface{}
	GetAll() []interface{}
	Search(k interface{}) (index int, contains bool)
	ElemType() reflect.Type
	CompareFunc() func(interface{}, interface{}) int8
}

type myKeys struct {
	container   []interface{}
	compareFunc func(interface{}, interface{}) int8
	elemType    reflect.Type
}

func NewKeys(compareFunc func(interface{}, interface{}) int8, elemType reflect.Type) *myKeys {
	return &myKeys{
		container:   make([]interface{}, 0),
		compareFunc: compareFunc,
		elemType:    elemType,
	}
}


func (keys *myKeys) Len() int {
	return len(keys.container)
}

func (keys *myKeys) Less(i, j int) bool {
	return keys.compareFunc(keys.container[i], keys.container[j]) < 0
}

func (keys *myKeys) Swap(i, j int) {
	keys.container[i], keys.container[j] = keys.container[j], keys.container[i]
}


func (keys *myKeys) isAcceptableElem(k interface{}) bool {
	if k == nil {
		return false
	}

	if reflect.TypeOf(k) != keys.elemType {
		return false
	}
	return true
}

func (keys *myKeys) Add(k interface{}) bool {
	if ok := keys.isAcceptableElem(k); !ok {
		return false
	}

	keys.container = append(keys.container, k)
	sort.Sort(keys)
	return true
}


func (keys *myKeys) Search(k interface{}) (index int, contains bool) {
	if ok := keys.isAcceptableElem(k); !ok {
		contains = false
		return
	}

	f := func(i int) bool { return keys.compareFunc(keys.container[i], k) >= 0 }
	index = sort.Search(keys.Len(), f)

	if index < keys.Len() && keys.container[index] == k {
		contains = true
	} else {
		contains = false
	}
	return
}

func (keys *myKeys) Remove(k interface{}) bool {
	if index, ok := keys.Search(k); !ok {
		return false
	} else {
		keys.container = append(keys.container[0:index], keys.container[index+1:]...)
	}
	return true
}


func (keys *myKeys) Clear() {
	keys.container = make([]interface{}, 0)
}


func (key *myKeys) Get(index int) interface{} {
	if index > key.Len() {
		return nil
	}
	return key.container[index]
}


func (key *myKeys) GetAll() []interface{} {
	initialLen := key.Len()
	snapshot := make([]interface{}, initialLen)
	actualLen := 0

	for _, key := range key.container {
		if actualLen < initialLen {
			snapshot[actualLen] = key
		} else {
			snapshot = append(snapshot, key)
		}
		actualLen++
	}
	if actualLen < initialLen {
		snapshot = snapshot[:actualLen]
	}
	return snapshot
}


func (key *myKeys) ElemType() reflect.Type {
	return key.elemType
}

//CompareFunc

func (key *myKeys) CompareFunc() func(interface{}, interface{}) int8 {
	return key.compareFunc
}

func (key *myKeys) String() string {
	var buf bytes.Buffer
	buf.WriteString("Set { ")
	for _, v := range key.container {
		buf.WriteString(fmt.Sprintf("%v ", v))
	}
	buf.WriteString("}")
	return buf.String()
}


type myOrderedMap struct {
	key      Keys
	elemType reflect.Type
	m        map[interface{}]interface{}
}

func NewOrderedMap(compareFunc func(interface{}, interface{}) int8, keyType reflect.Type, elemType reflect.Type) *myOrderedMap {
	var m *myOrderedMap

	m = new(myOrderedMap)

	m.key = (Keys)(NewKeys(compareFunc, keyType))

	m.elemType = elemType
	m.m = make(map[interface{}]interface{}, 0)
	return m
}

func (myOM *myOrderedMap) Get(key interface{}) interface{} {
	if key == nil {
		return nil
	}
	return myOM.m[key]
}

func (myOM *myOrderedMap) Put(key interface{}, elem interface{}) (interface{}, bool) {
	if key == nil || reflect.TypeOf(elem) != myOM.elemType {
		return nil, false
	}

	ret := myOM.m[key]
	myOM.m[key] = elem

	myOM.key.Add(key)

	return ret, true
}

func (myOM *myOrderedMap) Remove(key interface{}) interface{} {
	if key == nil {
		return nil
	}
	ret := myOM.m[key]
	if ret != nil {
		delete(myOM.m, key)
		myOM.key.Remove(key)
	}
	return ret
}

func (myOM *myOrderedMap) Clear() {
	myOM.key.Clear()
	myOM.m = make(map[interface{}]interface{}, 0)
}

func (myOM *myOrderedMap) Len() int {
	return myOM.key.Len()
}

func (myOM *myOrderedMap) Contains(key interface{}) bool {
	if key == nil {
		return false
	}

	if myOM.m[key] != nil {
		return true
	} else {
		return false
	}
}

func (myOM *myOrderedMap) FirstKey() interface{} {
	key := myOM.key.Get(0)
	return myOM.m[key]
}

func (myOM *myOrderedMap) LastKey() interface{} {
	length := myOM.key.Len()
	key := myOM.key.Get(length - 1)
	return myOM.m[key]
}

func (myOM *myOrderedMap) HeadMap(toKey interface{}) myMap.OrderedMap {
	if toKey == nil {
		return nil
	}

	om := myOrderedMap{
		key:      (Keys)(NewKeys(myOM.key.CompareFunc(), myOM.key.ElemType())),
		elemType: myOM.elemType,
		m:        make(map[interface{}]interface{}, 0),
	}

	s := myOM.key.GetAll()
	indexToKey, ok := myOM.key.Search(toKey)
	if !ok {
		return nil
	}
	for _, v := range s[:indexToKey] {
		om.Put(v, myOM.m[v])
	}

	return (myMap.OrderedMap)(&om)
}

func (myOM *myOrderedMap) SubMap(fromKey interface{}, toKey interface{}) myMap.OrderedMap {
	if toKey == nil || fromKey == nil {
		return nil
	}

	om := myOrderedMap{
		key:      (Keys)(NewKeys(myOM.key.CompareFunc(), myOM.key.ElemType())),
		elemType: myOM.elemType,
		m:        make(map[interface{}]interface{}, 0),
	}

	s := myOM.key.GetAll()
	indexToKey, _ := myOM.key.Search(toKey)

	indexFromKey, _ := myOM.key.Search(fromKey)

	for _, v := range s[indexFromKey:indexToKey] {
		om.Put(v, myOM.m[v])
	}

	return (myMap.OrderedMap)(&om)
}

func (myOM *myOrderedMap) TailMap(fromKey interface{}) myMap.OrderedMap {
	if fromKey == nil {
		return nil
	}

	om := myOrderedMap{
		key:      (Keys)(NewKeys(myOM.key.CompareFunc(), myOM.key.ElemType())),
		elemType: myOM.elemType,
		m:        make(map[interface{}]interface{}, 0),
	}

	s := myOM.key.GetAll()
	indexFromKey, ok := myOM.key.Search(fromKey)
	if !ok {
		return nil
	}
	for _, v := range s[indexFromKey:] {
		om.Put(v, myOM.m[v])
	}

	return (myMap.OrderedMap)(&om)
}

func (myOM *myOrderedMap) Keys() []interface{} {
	return myOM.key.GetAll()
}

func (myOM *myOrderedMap) Elems() []interface{} {
	s := myOM.key.GetAll()
	es := make([]interface{}, len(s))
	for _, v := range s {
		es = append(es, myOM.Get(v))
	}
	return es
}

func (myOM *myOrderedMap) ToMap() map[interface{}]interface{} {
	m := make(map[interface{}]interface{}, 0)
	s := myOM.key.GetAll()
	for _, v := range s {
		m[v] = myOM.Get(v)
	}
	return m
}

func (myOM *myOrderedMap) KeyType() reflect.Type {
	return myOM.key.ElemType()
}

func (myOM *myOrderedMap) ElemType() reflect.Type {
	return myOM.elemType
}


